package com.yanceysong.codetop.s71_s80;

import com.yanceysong.common.TreeNode;


public class S71_Easy_110_平衡二叉树 {
    /**
     * .<p>
     * .<a href="https://leetcode.cn/problems/balanced-binary-tree/">LeetCode 110. 平衡二叉树</a>
     * .<p>
     * .给定一个二叉树，判断它是否是高度平衡的二叉树。<br>
     * .高度平衡的定义：任意节点的左右子树高度差不超过 1。
     * .<p>
     * .核心标签：二叉树 | 深度优先搜索(DFS) | 递归 | 剪枝 | 高度计算
     * .<p>
     * .示例：
     * .1) 输入: root = [3,9,20,null,null,15,7]  输出: true
     * .   结构:
     * .         3
     * .        / \
     * .       9  20
     * .         /  \
     * .        15   7
     * .   每个节点左右高度差均 <= 1
     * .<p>
     * .2) 输入: root = [1,2,2,3,3,null,null,4,4] 输出: false
     * .   结构:
     * .             1
     * .            / \
     * .           2   2
     * .          / \
     * .         3   3
     * .        / \
     * .       4   4
     * .   节点值为1的左子树高度=4, 右子树高度=1, 差值=3 > 1 → 不平衡
     * .<p>
     * .思路对比：
     * .1. 朴素解法（自顶向下 Top-Down）: 对每个节点都调用一次 height() 计算左右高度，再判断是否平衡。时间复杂度最坏 O(n^2)。
     * .2. 优化解法（自底向上 Bottom-Up）: 在计算高度的同时，如果发现某个子树不平衡立刻返回 -1 作为“哨兵”并一路向上传递，避免重复计算。总体只遍历每个节点一次，时间复杂度 O(n)。
     * .<p>
     * .本实现采用优化解法：使用递归后序遍历 + 哨兵值 -1 表示不平衡，遇到不平衡立即向上传递，完成剪枝。
     * .<p>
     * .关键洞察：
     * .- 高度只需要知道左右子树是否平衡以及它们的高度，属于典型"后序遍历"场景。
     * .- 使用特殊返回值（哨兵）可以把“状态”折叠进高度计算过程，避免额外结构。
     * .- 一旦发现某处不平衡，无需继续计算其他分支的精确高度；剪枝节省时间。
     * .<p>
     * .ASCII 图解：
     * .平衡示例:
     * .       4
     * .      / \
     * .     2   6      → 节点4: 左高=2, 右高=2, 差=0
     * .    / \ / \
     * .   1  3 5  7   → 每个节点左右高度差 ≤ 1
     * .<p>
     * .不平衡示例（链式倾斜）:
     * .   1
     * .  /
     * . 2
     * ./
     * 3
     * . \  （在节点2: 左高=2, 右高=0 差=2 >1）
     * .  4
     * .<p>
     * .时间复杂度：O(n)  每个节点访问一次
     * .空间复杂度：O(h)  递归调用栈，h为树高度，最坏(链式)为 O(n)，最优(平衡)为 O(log n)
     * .<p>
     * .进一步拓展：
     * .- 若同时需要返回是否平衡与高度，可定义一个 Pair 对象；但使用哨兵更轻量。
     * .- 可迭代实现：需要手动维护栈与处理状态，复杂度与递归相同，但代码冗长。
     */
    public boolean isBalanced(TreeNode root) {
        // 当 checkHeight 返回 -1 说明存在不平衡
        return checkHeight(root) >= 0;
    }

    /**
     * .递归计算当前节点高度；若检测到不平衡则返回 -1 作为哨兵。
     * .后序遍历顺序：left → right → root
     * .@param node 当前节点
     * .@return 高度(>=0) 或 -1(不平衡)
     */
    private int checkHeight(TreeNode node) {
        if (node == null) {
            return 0; // 空节点高度为0
        }
        // 递归获取左子树高度
        int leftHeight = checkHeight(node.left);
        if (leftHeight == -1) {
            return -1; // 左子树已不平衡 → 直接向上传递
        }
        // 递归获取右子树高度
        int rightHeight = checkHeight(node.right);
        if (rightHeight == -1) {
            return -1; // 右子树已不平衡 → 直接向上传递
        }
        // 当前节点平衡性判定
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1; // 当前节点不平衡
        }
        // 若平衡，返回当前节点的高度 = 子树最大高度 + 1
        return Math.max(leftHeight, rightHeight) + 1;
    }

    /**
     * .朴素解法（仅用于对比）: 对每个节点重复计算高度。
     * .时间复杂度：最坏 O(n^2)
     */
    public boolean isBalancedTopDown(TreeNode root) {
        if (root == null) {
            return true;
        }
        int left = heightNaive(root.left);
        int right = heightNaive(root.right);
        if (Math.abs(left - right) > 1) {
            return false;
        }
        return isBalancedTopDown(root.left) && isBalancedTopDown(root.right);
    }

    // 朴素高度计算：单纯遍历整棵子树
    private int heightNaive(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return Math.max(heightNaive(node.left), heightNaive(node.right)) + 1;
    }

    /**
     * .构造一棵完全平衡的示例二叉树
     */
    private static TreeNode buildPerfectBalancedTree() {
        return new TreeNode(4,
                new TreeNode(2, new TreeNode(1), new TreeNode(3)),
                new TreeNode(6, new TreeNode(5), new TreeNode(7))
        );
    }

    /**
     * .构造一棵明显不平衡的链式左倾树: 1→2→3→4
     */
    private static TreeNode buildSkewedLeftTree() {
        TreeNode n4 = new TreeNode(4);
        TreeNode n3 = new TreeNode(3, n4, null);
        TreeNode n2 = new TreeNode(2, n3, null);
        return new TreeNode(1, n2, null);
    }

    /**
     * .构造一棵在深层才出现不平衡的树：
     * .           1
     * .          / \
     * .         2   3
     * .        / \
     * .       4   5
     * .      /
     * .     6
     */
    private static TreeNode buildDeepUnbalancedTree() {
        TreeNode n6 = new TreeNode(6);
        TreeNode n4 = new TreeNode(4, n6, null);
        TreeNode n5 = new TreeNode(5);
        TreeNode n2 = new TreeNode(2, n4, n5);
        TreeNode n3 = new TreeNode(3);
        return new TreeNode(1, n2, n3);
    }

    /**
     * .构造一棵“临界平衡”树：左右高度差均不超过1
     * .       10
     * .      /  \
     * .     5    15
     * .    /    /  \
     * .   3    12  18
     */
    private static TreeNode buildBorderlineBalancedTree() {
        TreeNode n3 = new TreeNode(3);
        TreeNode n5 = new TreeNode(5, n3, null);
        TreeNode n12 = new TreeNode(12);
        TreeNode n18 = new TreeNode(18);
        TreeNode n15 = new TreeNode(15, n12, n18);
        return new TreeNode(10, n5, n15);
    }

    /**
     * .构造一棵只有右子树的偏斜树
     */
    private static TreeNode buildSkewedRightTree(int depth) {
        TreeNode root = null;
        for (int i = depth; i >= 1; i--) {
            root = new TreeNode(i, null, root);
        }
        return root;
    }

    /**
     * .简单漂亮的打印测试结果辅助方法
     */
    private static void printResult(String title, boolean actual, boolean expected) {
        System.out.printf("%-28s -> 结果: %-5s 期望: %-5s %s%n",
                title,
                actual,
                expected,
                (actual == expected ? "✓" : "✗"));
    }

    public static void main(String[] args) {
        S71_Easy_110_平衡二叉树 solution = new S71_Easy_110_平衡二叉树();
        System.out.println("=== 平衡二叉树判定测试开始 ===\n");

        // 测试1: 空树
        TreeNode empty = null;
        printResult("测试1 空树", solution.isBalanced(empty), true);

        // 测试2: 单节点
        TreeNode single = new TreeNode(1);
        printResult("测试2 单节点", solution.isBalanced(single), true);

        // 测试3: 完全平衡树
        TreeNode perfect = buildPerfectBalancedTree();
        printResult("测试3 完全平衡树", solution.isBalanced(perfect), true);

        // 测试4: 左倾链式树 (明显不平衡)
        TreeNode skewLeft = buildSkewedLeftTree();
        printResult("测试4 左倾链式树", solution.isBalanced(skewLeft), false);

        // 测试5: 深层不平衡树 (上层看似平衡)
        TreeNode deepUnbalanced = buildDeepUnbalancedTree();
        printResult("测试5 深层不平衡", solution.isBalanced(deepUnbalanced), false);

        // 测试6: 临界平衡树 (所有差值 ≤ 1)
        TreeNode borderline = buildBorderlineBalancedTree();
        printResult("测试6 临界平衡树", solution.isBalanced(borderline), true);

        // 测试7: 只有右子树的偏斜树 depth=5
        TreeNode skewRight = buildSkewedRightTree(5); // 高度差不断扩大 → 不平衡
        printResult("测试7 右倾链式树", solution.isBalanced(skewRight), false);

        // 测试8: 对比朴素算法与优化算法（在深层不平衡树上）
        boolean fast = solution.isBalanced(deepUnbalanced);
        boolean slow = solution.isBalancedTopDown(deepUnbalanced);
        System.out.printf("测试8 对比两种算法 -> 优化: %s 朴素: %s 一致性: %s%n", fast, slow, (fast == slow ? "✓" : "✗"));

        // 测试9: 大致平衡但近似完全树 (手动构造)
        TreeNode nearPerfect = new TreeNode(8,
                new TreeNode(4,
                        new TreeNode(2, new TreeNode(1), new TreeNode(3)),
                        new TreeNode(6, new TreeNode(5), new TreeNode(7))
                ),
                new TreeNode(12,
                        new TreeNode(10, new TreeNode(9), new TreeNode(11)),
                        new TreeNode(14, new TreeNode(13), null) // 右侧缺一个叶子
                )
        );
        printResult("测试9 近似完全树", solution.isBalanced(nearPerfect), true);

        // 测试10: 人工构造高度差刚超过阈值的树
        TreeNode critical = new TreeNode(1,
                new TreeNode(2,
                        new TreeNode(3,
                                new TreeNode(4), null
                        ), null
                ), new TreeNode(5)
        ); // 左高=4 右高=2 差=2 → 不平衡
        printResult("测试10 临界不平衡", solution.isBalanced(critical), false);

        System.out.println("\n=== 所有测试结束 ===");
        System.out.println("提示: 若想使用断言验证, 运行时添加 JVM 参数 -ea 启用断言。");
    }
}
